#include "Heap.h"
#include <cstdlib>
#include <iostream>

Heap::Heap()
{
    data = NULL;
    length = 0;
};

Heap::Heap(int *datahead, int l)
{
    data = new int[l];
    for (int i = 0; i < l; i++)
	data[i] = datahead[i];
    length = l;
    for (int i = PARENT(l - 1); i >= 0; i--)
	shiftdown(i);
};

int Heap::rebuild(int *datahead, int l)
{
    if (data != NULL)
	delete[] data;
    data = new int[l];
    for (int i = 0; i < l; i++)
	data[i] = datahead[i];
    length = l;
    for (int i = PARENT(l - 1); i >= 0; i--)
	shiftdown(i);
    return 0;
};

Heap::~Heap()
{
    delete[] data;
};


int Heap::get_length()
{
    return length;
};

int Heap::get_height()
{
    int l = length;
    int digits = 1;
    while (l >>= 1 != 0)
	digits++;
    return digits;
};

bool Heap::is_empty()
{
    bool result = false;
    if (length == 0)
	result = true;
    return result;
};

int Heap::shiftdown(int i)
{
    int lc = LEFTCHILD(i);
    if (lc >= length)
	return 0;
    int child = lc;
    int rc = RIGHTCHILD(i);
    if (rc < length && data[rc] > data[lc])
	child = rc;
    if (data[i] < data[child])
    {
	int tmp = data[i];
	data[i] = data[child];
	data[child] = tmp;
	shiftdown(child);
    }
    else
	return 0;
};

int Heap::printout()
{
    for (int i = 0; i < length; i++)
	std::cout << data[i] << ", ";
    std::cout << "\b\b\n";
    return 0;
};

int Heap::sort()
{
    int l = length;
    while (length > 0)
    {
	int tmp = data[0];
	data[0] = data[length - 1];
	data[length - 1] = tmp;
	length--;
	shiftdown(0);
    }
    length = l;
    return 0;
};
